import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution15 {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> ans=new ArrayList<>();
        for (int i=0;i<nums.length;i++){
            while (i>0 && i<nums.length && nums[i]==nums[i-1]){
                i++;
            }
            int j=i+1,k=nums.length-1;
            while (j<k){
                if (nums[i]+nums[j]+nums[k]==0){
                    ans.add(Arrays.asList(nums[i],nums[j],nums[k]));
                    j++;
                    while (j<k && nums[j]==nums[j-1]){
                        j++;
                    }
                }else if (nums[i]+nums[j]+nums[k]>0){
                    k--;
                }else {
                    j++;
                }
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(new Solution15().threeSum(new int[]{-1,0,1,2,-1,-4}));
    }
}
